class Solution:
    def wiggleMaxLength(self, nums: list) -> int:
        length = len(nums)
        if length <= 1:
            return length
        up_list = [1] * length
        down_list = [1] * length
        up_max, down_max = 1, 1
        for i in range(1, length):
            for j in range(i - 1, -1, -1):
                if nums[i] > nums[j]:
                    up_list[i] = max(up_list[i], down_list[j] + 1)
                elif nums[i] < nums[j]:
                    down_list[i] = max(down_list[i], up_list[j] + 1)
                if up_list[i] > up_max and down_list[i] > down_max:
                    up_max, down_max = up_list[i], down_list[i]
                    break
        return max(max(up_list), max(down_list))


class Solution2:
    def wiggleMaxLength(self, nums: list) -> int:
        i = 1
        while i < len(nums):
            if nums[i] == nums[i - 1]:
                del nums[i]
            else:
                i += 1
        length = len(nums)
        if length <= 1:
            return length
        flag = nums[0] < nums[1]
        res = 1
        for i in range(1, length):
            if flag:
                if nums[i] > nums[i-1]:
                    res += 1
                    flag = False
            else:
                if nums[i] < nums[i-1]:
                    res += 1
                    flag = True
        return res


a = Solution2()
print(a.wiggleMaxLength([1, 7, 4, 9, 2, 5]))
print(a.wiggleMaxLength([1, 17, 5, 10, 13, 15, 10, 5, 16, 8]))
print(a.wiggleMaxLength([1, 2, 3, 4, 5, 6, 7, 8, 9]))
print(a.wiggleMaxLength([1,1,7,4,9,2,5]))
